Field of the Invention
This invention relates to a method of planning a route to a destination; it finds application in computer implemented systems that enable an optimal driving route to be planned.
Description of the Prior Art
Road travel is a major part of everyday life for business and other organizations, and for private individuals. The costs of traffic delays can be very large. The purely financial cost has been estimated as billions of pounds in the UK alone. Given these costs, systems which can assist drivers to optimize their travel, for instance by selecting the best route and by avoiding congestion delays, are of significant value. In fact a diverse array of driver information systems have grown up:
Longest established are broadcast radio traffic reports which aggregate data from a number of sources (police, eye-in-the-sky, and more recently mobile phone calls from drivers stuck in jams) to provide subjective advice about incidents and delays. Radio Data Systems RDS radios make these systems more effective by automatically cutting to traffic reports from normal radio programs.                Static route planning systems are provided on the web by major motoring organizations (AA, RAC). These allow a driver to enter the points of a journey and be given a route and driving instructions for that route.        GPS based in-vehicle personal navigation systems (PNS) have been introduced. These use the position of the vehicle and a route computed using a traditional static cost function to issue instructions to guide the driver to their destination. Such systems have begun to incorporate traffic information into their services, but this is not integrated into the route selection; the user can observe delays where they impact the selected route, and manually guide the system to re-plan a route avoiding the delayed sections of road if they consider this necessary.        Real time traffic monitoring systems, based on various technologies (e.g. mobile phones, fixed cameras, GPS fleet tracking) are being used to identify traffic delays and to feed the information into notification systems.        
As road congestion increases, systems providing route planning become more susceptible to error. A driver will not be pleased to ask for the fastest route from A to B, and then find themselves caught in a traffic jam for 50 minutes. Similarly, they will distrust a system which routes them along a busy A-road where they travel in convoy behind Heavy Goods Vehicle at 50 mph, while they could be traveling much faster on a slightly longer motorway route.
Known techniques for improved route planning require assigning individual road speeds to roads and sections of roads which more truly reflect the speed at which traffic can expect to travel on them. This assignment is generally static, that is to say that a section of road is assigned a fixed cost after surveying and analysis, and that cost is ever afterwards used as the cost of the road section in the routing algorithm. The cost can be reviewed, but this is as expensive as the original cost assignment. Hence, route planning algorithms in navigation devices work out route segment transit times using the road types defined in the map database stored on the device; an assumption may be made that vehicles on average travel at the legal speed limit for that type of road or some speed consistent with the class of the road. These map databases, from companies like TeleAtlas and NavTech, are the result of hugely costly and thorough surveying of roads, usually throughout an entire country. So the strength of this approach is that transit times can be estimated for every road in the map database. But its weakness is that the assumption of travel at the legal speed limit clearly breaks down for congested areas because the devices do not have reliable traffic information. The general approach for calculating a lowest cost route (e.g. quickest) can be thought of as comprehensive, but inaccurate if congestion occurs.
GPS portable satellite navigation devices with sophisticated route planning algorithms, such as the GO™ from TomTom International BV have become widespread in recent years and are used by large numbers of ordinary drivers: the benefits from integrating effective traffic data into these systems are considerable.
Prior art traffic monitoring systems have focussed on providing traffic flow data so that congestion can be avoided. But these systems have been limited mainly to major roads because of the infrastructure costs of developing the monitoring equipment (e.g. loop sensors buried in roads; camera based systems, such as number plate recognition systems) or because they rely on floating vehicle systems in which a relatively small proportion of all vehicles (equipped with dedicated hardware) are tracked, typically those moving on major roads and not urban areas. For commercial transportation companies, these limitation may be acceptable because their trucks mainly use the major roads anyway.
Overall, traffic monitoring services are not at all comprehensive, but useful when congestion occurs on a road that is monitored. But the usefulness is limited for two reasons. First, a user is merely informed of congestion; it is typically then down to the user to request appropriate action, such as to plan a new route, taking the congestion into account. Secondly, the congestion may have cleared by the time that the vehicle reaches the places that is indicated as being congested right now. Where congestion is predictable (i.e. it follows some kind of regularity or predictability in time, such as the morning rush hour, or congestion around a stadium when a major match is being played, or an accident that closes off one lane of a major road) then it is possible to estimate the possible congestion the vehicle will experience once it reaches the road that is currently congested. Time dependent traffic flow or transit time data (e.g. that at 8 am on each Monday morning, the transit time for a particular route segment is 20 minutes; it drops to 15 minutes at 1 pm and is 5 minutes at 11 pm etc.) can go some way to addressing this. Reference may be made to U.S. Pat. No. 6,356,836 and later WO 2004/021306. But to date, as noted above, this kind of data has typically only been applied to traffic monitoring systems that provide data for a relatively small proportion of roads in a country.
The overall effect is that a user can use route planning algorithms with time-dependent route segment costs, but is limited to route planning for the relatively small proportion of roads that are covered by the traffic monitoring system. Accuracy is provided at the expense of geographical coverage. Alternatively, a user can use route planning algorithms based on fixed, pre-defined route segment costs (e.g. the legal speed limit). Geographical coverage is available, but at the expense of accuracy.